package com.banmao.algorithm.No101To200.No112;

import java.util.LinkedList;

public class GenerateTreeNodeUtil {

    public static TreeNode generateTree(Integer[] array) {

        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode root = new TreeNode(array[0]);
        queue.add(root);

        // 题目中一般提供的示例是层序遍历
        int index = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.pollFirst();
                if(index >= array.length) {
                    break;
                }
                if (poll != null) {
                    Integer leftValue = array[index++];
                    Integer rightValue = array[index++];
                    poll.left = leftValue == null ? null : new TreeNode(leftValue);
                    queue.add(poll.left);
                    poll.right = rightValue == null ? null : new TreeNode(rightValue);
                    queue.add(poll.right);
                }
            }
        }

        return root;

    }

}
